package org.hot100.h300;

import java.util.Arrays;

/**
 * @Author yu
 * @Date 2022/3/4
 */
public class Solution {

    public static void main(String[] args) {

        int[] ints = {10,9,2,5,3,7,101,18};

        Solution solution = new Solution();
        System.out.println(solution.lengthOfLIS4(ints));

    }

/*    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return nums.length == 0 ? 0 : 1;
        }

        int max = 0;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        return max;
    }*/

    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return nums.length == 0 ? 0 : 1;
        }

        // dp[i] 所有元素置 1，含义是每个元素都至少可以单独成为子序列，此时长度都为 1。
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        
        int max = 0;

        // 10,9,2,5,3,7,101,18
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {

                // 比较当前元素是否小于后一个元素
                if (nums[j] < nums[i]) {

                    // if 成立，将后一个元素子序列长度改为 dp[j] + 1
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }

        return max;
    }

    public int lengthOfLIS2(int[] nums) {
        int[] temp = new int[nums.length];
        int max = 0;
        Arrays.fill(temp, 1);

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    temp[i] = Math.max(temp[i], temp[j] + 1);
                }
            }
            max = Math.max(max, temp[i]);
        }

        return max;
    }

    public int lengthOfLIS3(int[] nums) {
        int[] res = new int[nums.length];
        int sum = 0;
        Arrays.fill(res, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    res[i] = Math.max(res[i], res[j] + 1);
                }
            }
            sum = Math.max(sum, res[i]);
        }
        return sum;
    }

    // 10 9 2 5 3 7 101 18
    // 1  1 1 2 2 3 4   4
    public int lengthOfLIS4(int[] nums) {
        int[] temp = new int[nums.length];
        int max = 0;
        Arrays.fill(temp, 1);
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    temp[i] = Math.max(temp[i], temp[j] + 1);
                }
            }
            max = Math.max(max, temp[i]);
        }
        return max;
    }
}
